答案为所有的回文串组合-不相交的回文串组合。
记 为回文串个数 , 可以通过计算每个节点的回文串数量求得。
不相交的回文组合也比较好求,先算出以 为左端点和右端点的回文串数量 , 。
不相交的回文组合个数为:
将 数组做一遍后缀和即可解决问题 , 注意中间的取模。
空间只有 , 用朴素的数组存图要炸掉。
这道题除了卡空间,就没有什么难点了。
实现时用邻接表代替,为了方便打了一个函数找边,常数大了几十倍。
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
#define Mod 51123987
const int MAXN = 2000000;
#pragma GCC pack(1)
struct Palindrome_Automaton {
int Size , Last , Root0 , Root1 , Link[ MAXN + 5 ];
int n; char Str[ MAXN + 5 ];
int Len[ MAXN + 5 ] , Cnt[ MAXN + 5 ] , End[ MAXN + 5 ];
int Ans , L[ MAXN + 5 ] , R[ MAXN + 5 ];
vector< pair< char , int > > Trans[ MAXN + 5 ];
void Init( ) {
Size = 0; n = 0;
for( int i = 0 ; i <= MAXN ; i ++ ) Trans[ i ].clear( );
memset( Link , 0 , sizeof( Link ) );
memset( Len , 0 , sizeof( Len ) );
Root0 = Size ++ , Root1 = Size ++; Last = Root1;
Len[ Root0 ] = 0 , Link[ Root0 ] = Root1;
Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
}
int chk( long long x ) {
if( x >= Mod ) x %= Mod;
return x;
}
int Finde( int u , char ch ) {
for( int i = 0 ; i < Trans[ u ].size( ) ; i ++ )
if( Trans[ u ][ i ].first == ch ) return Trans[ u ][ i ].second;
return 0;
}
int Extend( char ch ) {
int u = Last; Str[ ++ n ] = ch;
for( ; Str[ n ] != Str[ n - Len[ u ] - 1 ] ; u = Link[ u ] );
if( !Finde( u , ch ) ) {
int Newnode = ++ Size , v = Link[ u ];
Len[ Newnode ] = Len[ u ] + 2;
for( ; Str[ n ] != Str[ n - Len[ v ] - 1 ] ; v = Link[ v ] );
Link[ Newnode ] = Finde( v , ch ); Trans[ u ].push_back( { ch , Newnode } );
End[ Newnode ] = End[ Link[ Newnode ] ] + 1;
}
Cnt[ Last = Finde( u , ch ) ] ++;
return End[ Last ];
}
void Build1( char *str ) {
Init( );
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
R[ i ] = Extend( str[ i ] );
for( int i = Size ; i >= 2 ; i -- )
Cnt[ Link[ i ] ] = chk( Cnt[ Link[ i ] ] + Cnt[ i ] ) , Ans = chk( Ans + Cnt[ i ] );
Ans = chk( chk( 1ll * Ans * chk( Ans - 1 + Mod ) ) * 25561994ll );
}
void Build2( char *str ) {
Init( );
int len = strlen( str );
for( int i = len - 1 ; i >= 0 ; i -- )
L[ i ] = Extend( str[ i ] );
}
int Calc( ) {
n --;
for( int i = n - 1 ; i >= 0 ; i -- )
L[ i ] = ( L[ i ] + L[ i + 1 ] ) % Mod;
for( int i = 0 ; i < n ; i ++ )
Ans = chk( Ans - chk( 1ll * R[ i ] * L[ i + 1 ] ) + Mod );
return Ans;
}
}PAM;
int n;
char str[ MAXN + 5 ];
int main() {
scanf("%d\n%s", &n , str );
PAM.Build1( str );
PAM.Build2( str );
printf("%d", PAM.Calc( ) );
return 0;
}